
(function(window,document,Laya){
	var __un=Laya.un,__uns=Laya.uns,__static=Laya.static,__class=Laya.class,__getset=Laya.getset,__newvec=Laya.__newvec;
	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.core.DiagonalMovement
	var DiagonalMovement=(function(){
		function DiagonalMovement(){}
		__class(DiagonalMovement,'PathFinding.core.DiagonalMovement');
		DiagonalMovement.Always=1;
		DiagonalMovement.Never=2;
		DiagonalMovement.IfAtMostOneObstacle=3;
		DiagonalMovement.OnlyWhenNoObstacles=4;
		return DiagonalMovement;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.core.Grid
	var Grid=(function(){
		function Grid(width_or_matrix,height,matrix){
			this.width=0;
			this.height=0;
			this.nodes=null;
			var width=0;
			if ((typeof width_or_matrix=='number')){
				width=width_or_matrix;
			}
			else{
				height=width_or_matrix.length;
				width=width_or_matrix[0].length;
				matrix=width_or_matrix;
			}
			this.width=width;
			this.height=height;
			this.nodes=this._buildNodes(width,height,matrix);
		}

		__class(Grid,'PathFinding.core.Grid');
		var __proto=Grid.prototype;
		/**
		*Build and return the nodes.
		*@private
		*@param {number}width
		*@param {number}height
		*@param {Array<Array<number|boolean>>}[matrix]-A 0-1 matrix representing
		*the walkable status of the nodes.
		*@see Grid
		*/
		__proto._buildNodes=function(width,height,matrix){
			var i=0,j=0,nodes=[];
			for (i=0;i < height;++i){
				nodes[i]=[];
				for (j=0;j < width;++j){
					nodes[i][j]=new Node1(j,i);
				}
			}
			if (matrix==null){
				return nodes;
			}
			if (matrix.length !=height || matrix[0].length !=width){
				throw new Error('Matrix size does not fit');
			}
			for (i=0;i < height;++i){
				for (j=0;j < width;++j){
					if (matrix[i][j]){
						nodes[i][j].walkable=false;
					}
				}
			}
			return nodes;
		}

		__proto.getNodeAt=function(x,y){
			return this.nodes[y][x];
		}

		/**
		*Determine whether the node at the given position is walkable.
		*(Also returns false if the position is outside the grid.)
		*@param {number}x-The x coordinate of the node.
		*@param {number}y-The y coordinate of the node.
		*@return {boolean}-The walkability of the node.
		*/
		__proto.isWalkableAt=function(x,y){
			return this.isInside(x,y)&& this.nodes[y][x].walkable;
		}

		/**
		*Determine whether the position is inside the grid.
		*XXX:`grid.isInside(x,y)` is wierd to read.
		*It should be `(x,y)is inside grid`,but I failed to find a better
		*name for this method.
		*@param {number}x
		*@param {number}y
		*@return {boolean}
		*/
		__proto.isInside=function(x,y){
			return (x >=0 && x < this.width)&& (y >=0 && y < this.height);
		}

		/**
		*Set whether the node on the given position is walkable.
		*NOTE:throws exception if the coordinate is not inside the grid.
		*@param {number}x-The x coordinate of the node.
		*@param {number}y-The y coordinate of the node.
		*@param {boolean}walkable-Whether the position is walkable.
		*/
		__proto.setWalkableAt=function(x,y,walkable){
			this.nodes[y][x].walkable=walkable;
		}

		/**
		*Get the neighbors of the given node.
		*
		*offsets diagonalOffsets:
		*+---+---+---++---+---+---+
		*| | 0 | | | 0 | | 1 |
		*+---+---+---++---+---+---+
		*| 3 | | 1 | | | | |
		*+---+---+---++---+---+---+
		*| | 2 | | | 3 | | 2 |
		*+---+---+---++---+---+---+
		*
		*When allowDiagonal is true,if offsets[i] is valid,then
		*diagonalOffsets[i] and
		*diagonalOffsets[(i+1)% 4] is valid.
		*@param {Node}node
		*@param {diagonalMovement}diagonalMovement
		*/
		__proto.getNeighbors=function(node,diagonalMovement){
			var x=node.x,y=node.y,neighbors=[],s0=false,d0=false,s1=false,d1=false,s2=false,d2=false,s3=false,d3=false,nodes=this.nodes;
			if (this.isWalkableAt(x,y-1)){
				neighbors.push(nodes[y-1][x]);
				s0=true;
			}
			if (this.isWalkableAt(x+1,y)){
				neighbors.push(nodes[y][x+1]);
				s1=true;
			}
			if (this.isWalkableAt(x,y+1)){
				neighbors.push(nodes[y+1][x]);
				s2=true;
			}
			if (this.isWalkableAt(x-1,y)){
				neighbors.push(nodes[y][x-1]);
				s3=true;
			}
			if (diagonalMovement==DiagonalMovement.Never){
				return neighbors;
			}
			if (diagonalMovement==DiagonalMovement.OnlyWhenNoObstacles){
				d0=s3 && s0;
				d1=s0 && s1;
				d2=s1 && s2;
				d3=s2 && s3;
			}
			else if (diagonalMovement==DiagonalMovement.IfAtMostOneObstacle){
				d0=s3 || s0;
				d1=s0 || s1;
				d2=s1 || s2;
				d3=s2 || s3;
			}
			else if (diagonalMovement==DiagonalMovement.Always){
				d0=true;
				d1=true;
				d2=true;
				d3=true;
			}
			else{
				throw new Error('Incorrect value of diagonalMovement');
			}
			if (d0 && this.isWalkableAt(x-1,y-1)){
				neighbors.push(nodes[y-1][x-1]);
			}
			if (d1 && this.isWalkableAt(x+1,y-1)){
				neighbors.push(nodes[y-1][x+1]);
			}
			if (d2 && this.isWalkableAt(x+1,y+1)){
				neighbors.push(nodes[y+1][x+1]);
			}
			if (d3 && this.isWalkableAt(x-1,y+1)){
				neighbors.push(nodes[y+1][x-1]);
			}
			return neighbors;
		}

		/**
		*Get a clone of this grid.
		*@return {Grid}Cloned grid.
		*/
		__proto.clone=function(){
			var i=0,j=0,
			width=this.width,height=this.height,thisNodes=this.nodes,
			newGrid=new Grid(width,height),newNodes=[];
			for (i=0;i < height;++i){
				newNodes[i]=[];
				for (j=0;j < width;++j){
					newNodes[i][j]=new Node1(j,i,thisNodes[i][j].walkable);
				}
			}
			newGrid.nodes=newNodes;
			return newGrid;
		}

		__proto.reset=function(){
			var _node;
			for (var i=0;i < this.height;++i){
				for (var j=0;j < this.width;++j){
					_node=this.nodes[i][j];
					_node.g=0;
					_node.f=0;
					_node.h=0;
					_node.by=0;
					_node.parent=null;
					_node.opened=null;
					_node.closed=null;
					_node.tested=null;
				}
			}
		}

		return Grid;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.core.Heuristic
	var Heuristic=(function(){
		function Heuristic(){}
		__class(Heuristic,'PathFinding.core.Heuristic');
		Heuristic.manhattan=function(dx,dy){
			return dx+dy;
		}

		Heuristic.euclidean=function(dx,dy){
			return Math.sqrt(dx *dx+dy *dy);
		}

		Heuristic.octile=function(dx,dy){
			var F=Math.SQRT2-1;
			return (dx < dy)? F *dx+dy :F *dy+dx;
		}

		Heuristic.chebyshev=function(dx,dy){
			return Math.max(dx,dy);
		}

		return Heuristic;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.core.Node
	var Node1=(function(){
		function Node(x,y,walkable){
			this.x=0;
			this.y=0;
			this.g=0;
			this.f=0;
			this.h=0;
			this.by=0;
			this.parent=null;
			this.opened=null;
			this.closed=null;
			this.tested=null;
			this.walkable=false;
			(walkable===void 0)&& (walkable=true);
			this.x=x;
			this.y=y;
			this.walkable=walkable;
		}

		__class(Node,'PathFinding.core.Node',null,'Node1');
		return Node;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.core.Util
	var Util=(function(){
		function Util(){}
		__class(Util,'PathFinding.core.Util');
		Util.backtrace=function(node){
			var path=[[node.x,node.y]];
			while (node.parent){
				node=node.parent;
				path.push([node.x,node.y]);
			}
			return path.reverse();
		}

		Util.biBacktrace=function(nodeA,nodeB){
			var pathA=Util.backtrace(nodeA),pathB=Util.backtrace(nodeB);
			return pathA.concat(pathB.reverse());
		}

		Util.pathLength=function(path){
			var i=0,sum=0,a=0,b=0,dx=0,dy=0;
			for (i=1;i < path.length;++i){
				a=path[i-1];
				b=path[i];
				dx=a[0]-b[0];
				dy=a[1]-b[1];
				sum+=Math.sqrt(dx *dx+dy *dy);
			}
			return sum;
		}

		Util.interpolate=function(x0,y0,x1,y1){
			var abs=Math.abs,line=[],sx=0,sy=0,dx=0,dy=0,err=0,e2=0;
			dx=abs(x1-x0);
			dy=abs(y1-y0);
			sx=(x0 < x1)? 1 :-1;
			sy=(y0 < y1)? 1 :-1;
			err=dx-dy;
			while (true){
				line.push([x0,y0]);
				if (x0==x1 && y0==y1){
					break ;
				}
				e2=2 *err;
				if (e2 >-dy){
					err=err-dy;
					x0=x0+sx;
				}
				if (e2 < dx){
					err=err+dx;
					y0=y0+sy;
				}
			}
			return line;
		}

		Util.expandPath=function(path){
			var expanded=[],len=path.length,coord0,coord1,interpolated,interpolatedLen=0,i=0,j=0;
			if (len < 2){
				return expanded;
			}
			for (i=0;i < len-1;++i){
				coord0=path[i];
				coord1=path[i+1];
				interpolated=Util.interpolate(coord0[0],coord0[1],coord1[0],coord1[1]);
				interpolatedLen=interpolated.length;
				for (j=0;j < interpolatedLen-1;++j){
					expanded.push(interpolated[j]);
				}
			}
			expanded.push(path[len-1]);
			return expanded;
		}

		Util.smoothenPath=function(grid,path){
			var len=path.length,x0=path[0][0],
			y0=path[0][1],
			x1=path[len-1][0],
			y1=path[len-1][1],
			sx=0,sy=0,
			ex=0,ey=0,
			newPath,i=0,j=0,coord,line,testCoord,blocked=false,lastValidCoord;
			sx=x0;
			sy=y0;
			newPath=[[sx,sy]];
			for (i=2;i < len;++i){
				coord=path[i];
				ex=coord[0];
				ey=coord[1];
				line=Util.interpolate(sx,sy,ex,ey);
				blocked=false;
				for (j=1;j < line.length;++j){
					testCoord=line[j];
					if (!grid.isWalkableAt(testCoord[0],testCoord[1])){
						blocked=true;
						break ;
					}
				}
				if (blocked){
					lastValidCoord=path[i-1];
					newPath.push(lastValidCoord);
					sx=lastValidCoord[0];
					sy=lastValidCoord[1];
				}
			}
			newPath.push([x1,y1]);
			return newPath;
		}

		Util.compressPath=function(path){
			if (path.length < 3){
				return path;
			};
			var compressed=[],sx=path[0][0],
			sy=path[0][1],
			px=path[1][0],
			py=path[1][1],
			dx=px-sx,
			dy=py-sy,
			lx=0,ly=0,ldx=0,ldy=0,sq=NaN,i=0;
			sq=Math.sqrt(dx *dx+dy *dy);
			dx /=sq;
			dy /=sq;
			compressed.push([sx,sy]);
			for (i=2;i < path.length;i++){
				lx=px;
				ly=py;
				ldx=dx;
				ldy=dy;
				px=path[i][0];
				py=path[i][1];
				dx=px-lx;
				dy=py-ly;
				sq=Math.sqrt(dx *dx+dy *dy);
				dx /=sq;
				dy /=sq;
				if (dx!==ldx || dy!==ldy){
					compressed.push([lx,ly]);
				}
			}
			compressed.push([px,py]);
			return compressed;
		}

		return Util;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.finders.AStarFinder
	var AStarFinder=(function(){
		function AStarFinder(opt){
			this.allowDiagonal=false;
			this.dontCrossCorners=false;
			this.heuristic=null;
			this.weight=0;
			this.diagonalMovement=0;
			opt=opt || {};
			this.allowDiagonal=opt.allowDiagonal;
			this.dontCrossCorners=opt.dontCrossCorners;
			this.heuristic=opt.heuristic || Heuristic.manhattan;
			this.weight=opt.weight || 1;
			this.diagonalMovement=opt.diagonalMovement;
			if (!this.diagonalMovement){
				if (!this.allowDiagonal){
					this.diagonalMovement=DiagonalMovement.Never;
				}
				else{
					if (this.dontCrossCorners){
						this.diagonalMovement=DiagonalMovement.OnlyWhenNoObstacles;
					}
					else{
						this.diagonalMovement=DiagonalMovement.IfAtMostOneObstacle;
					}
				}
			}
			if (this.diagonalMovement===DiagonalMovement.Never){
				this.heuristic=opt.heuristic || Heuristic.manhattan;
			}
			else{
				this.heuristic=opt.heuristic || Heuristic.octile;
			}
		}

		__class(AStarFinder,'PathFinding.finders.AStarFinder');
		var __proto=AStarFinder.prototype;
		/**
		*Find and return the the path.
		*@return {Array<Array<number>>}The path,including both start and
		*end positions.
		*/
		__proto.findPath=function(startX,startY,endX,endY,grid){
			var openList=new Heap(function(nodeA,nodeB){
				return nodeA.f-nodeB.f;
			}),startNode=grid.getNodeAt(startX,startY),endNode=grid.getNodeAt(endX,endY),heuristic=this.heuristic,diagonalMovement=this.diagonalMovement,weight=this.weight,abs=Math.abs,SQRT2=Math.SQRT2,node,neighbors,neighbor,i=0,l=0,x=0,y=0,ng=0;
			startNode.g=0;
			startNode.f=0;
			openList.push(startNode);
			startNode.opened=true;
			while (!openList.empty()){
				node=openList.pop();
				node.closed=true;
				if (node===endNode){
					return Util.backtrace(endNode);
				}
				neighbors=grid.getNeighbors(node,diagonalMovement);
				for (i=0,l=neighbors.length;i < l;++i){
					neighbor=neighbors[i];
					if (neighbor.closed){
						continue ;
					}
					x=neighbor.x;
					y=neighbor.y;
					ng=node.g+((x-node.x===0 || y-node.y===0)? 1 :SQRT2);
					if (!neighbor.opened || ng < neighbor.g){
						neighbor.g=ng;
						neighbor.h=neighbor.h || weight *heuristic(abs(x-endX),abs(y-endY));
						neighbor.f=neighbor.g+neighbor.h;
						neighbor.parent=node;
						if (!neighbor.opened){
							openList.push(neighbor);
							neighbor.opened=true;
						}
						else{
							openList.updateItem(neighbor);
						}
					}
				}
			}
			return [];
		}

		return AStarFinder;
	})()


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.BiAStarFinder
	var BiAStarFinder=(function(){
		function BiAStarFinder(opt){
			this.allowDiagonal=false;
			this.dontCrossCorners=false;
			this.diagonalMovement=0;
			this.heuristic=null;
			this.weight=0;
			opt=opt || {};
			this.allowDiagonal=opt.allowDiagonal;
			this.dontCrossCorners=opt.dontCrossCorners;
			this.diagonalMovement=opt.diagonalMovement;
			this.heuristic=opt.heuristic || Heuristic.manhattan;
			this.weight=opt.weight || 1;
			if (!this.diagonalMovement){
				if (!this.allowDiagonal){
					this.diagonalMovement=DiagonalMovement.Never;
				}
				else{
					if (this.dontCrossCorners){
						this.diagonalMovement=DiagonalMovement.OnlyWhenNoObstacles;
					}
					else{
						this.diagonalMovement=DiagonalMovement.IfAtMostOneObstacle;
					}
				}
			}
			if (this.diagonalMovement==DiagonalMovement.Never){
				this.heuristic=opt.heuristic || Heuristic.manhattan;
			}
			else{
				this.heuristic=opt.heuristic || Heuristic.octile;
			}
		}

		__class(BiAStarFinder,'PathFinding.finders.BiAStarFinder');
		var __proto=BiAStarFinder.prototype;
		/**
		*Find and return the the path.
		*@return {Array<Array<number>>}The path,including both start and
		*end positions.
		*/
		__proto.findPath=function(startX,startY,endX,endY,grid){
			var cmp=function (nodeA,nodeB){
				return nodeA.f-nodeB.f;
			};
			var startOpenList=new Heap(cmp),endOpenList=new Heap(cmp),startNode=grid.getNodeAt(startX,startY),endNode=grid.getNodeAt(endX,endY),heuristic=this.heuristic,diagonalMovement=this.diagonalMovement,weight=this.weight,abs=Math.abs,SQRT2=Math.SQRT2,node,neighbors,neighbor,i=0,l=0,x=0,y=0,ng=0,BY_START=1,BY_END=2;
			startNode.g=0;
			startNode.f=0;
			startOpenList.push(startNode);
			startNode.opened=BY_START;
			endNode.g=0;
			endNode.f=0;
			endOpenList.push(endNode);
			endNode.opened=BY_END;
			while (!startOpenList.empty()&& !endOpenList.empty()){
				node=startOpenList.pop();
				node.closed=true;
				neighbors=grid.getNeighbors(node,diagonalMovement);
				for (i=0,l=neighbors.length;i < l;++i){
					neighbor=neighbors[i];
					if (neighbor.closed){
						continue ;
					}
					if (neighbor.opened===BY_END){
						return Util.biBacktrace(node,neighbor);
					}
					x=neighbor.x;
					y=neighbor.y;
					ng=node.g+((x-node.x===0 || y-node.y===0)? 1 :SQRT2);
					if (!neighbor.opened || ng < neighbor.g){
						neighbor.g=ng;
						neighbor.h=neighbor.h || weight *heuristic(abs(x-endX),abs(y-endY));
						neighbor.f=neighbor.g+neighbor.h;
						neighbor.parent=node;
						if (!neighbor.opened){
							startOpenList.push(neighbor);
							neighbor.opened=BY_START;
						}
						else{
							startOpenList.updateItem(neighbor);
						}
					}
				}
				node=endOpenList.pop();
				node.closed=true;
				neighbors=grid.getNeighbors(node,diagonalMovement);
				for (i=0,l=neighbors.length;i < l;++i){
					neighbor=neighbors[i];
					if (neighbor.closed){
						continue ;
					}
					if (neighbor.opened===BY_START){
						return Util.biBacktrace(neighbor,node);
					}
					x=neighbor.x;
					y=neighbor.y;
					ng=node.g+((x-node.x===0 || y-node.y===0)? 1 :SQRT2);
					if (!neighbor.opened || ng < neighbor.g){
						neighbor.g=ng;
						neighbor.h=neighbor.h || weight *heuristic(abs(x-startX),abs(y-startY));
						neighbor.f=neighbor.g+neighbor.h;
						neighbor.parent=node;
						if (!neighbor.opened){
							endOpenList.push(neighbor);
							neighbor.opened=BY_END;
						}
						else{
							endOpenList.updateItem(neighbor);
						}
					}
				}
			}
			return [];
		}

		return BiAStarFinder;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.finders.BiBreadthFirstFinder
	var BiBreadthFirstFinder=(function(){
		function BiBreadthFirstFinder(opt){
			this.allowDiagonal=false;
			this.dontCrossCorners=false;
			this.heuristic=null;
			this.weight=0;
			this.diagonalMovement=0;
			opt=opt || {};
			this.allowDiagonal=opt.allowDiagonal;
			this.dontCrossCorners=opt.dontCrossCorners;
			this.diagonalMovement=opt.diagonalMovement;
			if (!this.diagonalMovement){
				if (!this.allowDiagonal){
					this.diagonalMovement=DiagonalMovement.Never;
				}
				else{
					if (this.dontCrossCorners){
						this.diagonalMovement=DiagonalMovement.OnlyWhenNoObstacles;
					}
					else{
						this.diagonalMovement=DiagonalMovement.IfAtMostOneObstacle;
					}
				}
			}
		}

		__class(BiBreadthFirstFinder,'PathFinding.finders.BiBreadthFirstFinder');
		var __proto=BiBreadthFirstFinder.prototype;
		/**
		*Find and return the the path.
		*@return {Array<Array<number>>}The path,including both start and
		*end positions.
		*/
		__proto.findPath=function(startX,startY,endX,endY,grid){
			var startNode=grid.getNodeAt(startX,startY),endNode=grid.getNodeAt(endX,endY),startOpenList=[],endOpenList=[],neighbors,neighbor,node,diagonalMovement=this.diagonalMovement,BY_START=0,BY_END=1,i=0,l=0;
			startOpenList.push(startNode);
			startNode.opened=true;
			startNode.by=BY_START;
			endOpenList.push(endNode);
			endNode.opened=true;
			endNode.by=BY_END;
			while (startOpenList.length && endOpenList.length){
				node=startOpenList.shift();
				node.closed=true;
				neighbors=grid.getNeighbors(node,diagonalMovement);
				for (i=0,l=neighbors.length;i < l;++i){
					neighbor=neighbors[i];
					if (neighbor.closed){
						continue ;
					}
					if (neighbor.opened){
						if (neighbor.by===BY_END){
							return Util.biBacktrace(node,neighbor);
						}
						continue ;
					}
					startOpenList.push(neighbor);
					neighbor.parent=node;
					neighbor.opened=true;
					neighbor.by=BY_START;
				}
				node=endOpenList.shift();
				node.closed=true;
				neighbors=grid.getNeighbors(node,diagonalMovement);
				for (i=0,l=neighbors.length;i < l;++i){
					neighbor=neighbors[i];
					if (neighbor.closed){
						continue ;
					}
					if (neighbor.opened){
						if (neighbor.by===BY_START){
							return Util.biBacktrace(neighbor,node);
						}
						continue ;
					}
					endOpenList.push(neighbor);
					neighbor.parent=node;
					neighbor.opened=true;
					neighbor.by=BY_END;
				}
			}
			return [];
		}

		return BiBreadthFirstFinder;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.finders.BreadthFirstFinder
	var BreadthFirstFinder=(function(){
		function BreadthFirstFinder(opt){
			this.allowDiagonal=false;
			this.dontCrossCorners=false;
			this.heuristic=null;
			this.weight=0;
			this.diagonalMovement=0;
			opt=opt || {};
			this.allowDiagonal=opt.allowDiagonal;
			this.dontCrossCorners=opt.dontCrossCorners;
			this.diagonalMovement=opt.diagonalMovement;
			if (!this.diagonalMovement){
				if (!this.allowDiagonal){
					this.diagonalMovement=DiagonalMovement.Never;
				}
				else{
					if (this.dontCrossCorners){
						this.diagonalMovement=DiagonalMovement.OnlyWhenNoObstacles;
					}
					else{
						this.diagonalMovement=DiagonalMovement.IfAtMostOneObstacle;
					}
				}
			}
		}

		__class(BreadthFirstFinder,'PathFinding.finders.BreadthFirstFinder');
		var __proto=BreadthFirstFinder.prototype;
		/**
		*Find and return the the path.
		*@return {Array<Array<number>>}The path,including both start and
		*end positions.
		*/
		__proto.findPath=function(startX,startY,endX,endY,grid){
			var openList=[],diagonalMovement=this.diagonalMovement,startNode=grid.getNodeAt(startX,startY),endNode=grid.getNodeAt(endX,endY),neighbors,neighbor,node,i=0,l=0;
			openList.push(startNode);
			startNode.opened=true;
			while (openList.length){
				node=openList.shift();
				node.closed=true;
				if (node===endNode){
					return Util.backtrace(endNode);
				}
				neighbors=grid.getNeighbors(node,diagonalMovement);
				for (i=0,l=neighbors.length;i < l;++i){
					neighbor=neighbors[i];
					if (neighbor.closed || neighbor.opened){
						continue ;
					}
					openList.push(neighbor);
					neighbor.opened=true;
					neighbor.parent=node;
				}
			}
			return [];
		}

		return BreadthFirstFinder;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.finders.IDAStarFinder
	var IDAStarFinder=(function(){
		function IDAStarFinder(opt){
			this.allowDiagonal=false;
			this.dontCrossCorners=false;
			this.heuristic=null;
			this.weight=0;
			this.diagonalMovement=0;
			this.trackRecursion=false;
			this.timeLimit=NaN;
			opt=opt || {};
			this.allowDiagonal=opt.allowDiagonal;
			this.dontCrossCorners=opt.dontCrossCorners;
			this.diagonalMovement=opt.diagonalMovement;
			this.heuristic=opt.heuristic || Heuristic.manhattan;
			this.weight=opt.weight || 1;
			this.trackRecursion=opt.trackRecursion || false;
			this.timeLimit=opt.timeLimit || Infinity;
			if (!this.diagonalMovement){
				if (!this.allowDiagonal){
					this.diagonalMovement=DiagonalMovement.Never;
				}
				else{
					if (this.dontCrossCorners){
						this.diagonalMovement=DiagonalMovement.OnlyWhenNoObstacles;
					}
					else{
						this.diagonalMovement=DiagonalMovement.IfAtMostOneObstacle;
					}
				}
			}
			if (this.diagonalMovement===DiagonalMovement.Never){
				this.heuristic=opt.heuristic || Heuristic.manhattan;
			}
			else{
				this.heuristic=opt.heuristic || Heuristic.octile;
			}
		}

		__class(IDAStarFinder,'PathFinding.finders.IDAStarFinder');
		var __proto=IDAStarFinder.prototype;
		/**
		*Find and return the the path. When an empty array is returned,either
		*no path is possible,or the maximum execution time is reached.
		*
		*@return {Array<Array<number>>}The path,including both start and
		*end positions.
		*/
		__proto.findPath=function(startX,startY,endX,endY,grid){
			var _$this=this;
			var nodesVisited=0;
			var startTime=new Date().getTime();
			var h=function (a,b){
				return _$this.heuristic(Math.abs(b.x-a.x),Math.abs(b.y-a.y));
			}.bind(this);
			var cost=function (a,b){
				return (a.x===b.x || a.y===b.y)? 1 :Math.SQRT2;
			};
			var search=function (node,g,cutoff,route,depth){
				nodesVisited++;
				if (_$this.timeLimit > 0 && new Date().getTime()-startTime > _$this.timeLimit *1000){
					return Infinity;
				};
				var f=g+h(node,end)*_$this.weight;
				if (f > cutoff){
					return f;
				}
				if (node==end){
					route[depth]=[node.x,node.y];
					return node;
				};
				var min=0,t=0,k=0,neighbour;
				var neighbours=grid.getNeighbors(node,_$this.diagonalMovement);
				for (k=0,min=Infinity;neighbour=neighbours[k];++k){
					if (_$this.trackRecursion){
						neighbour.retainCount=neighbour.retainCount+1 || 1;
						if (neighbour.tested !=true){
							neighbour.tested=true;
						}
					}
					t=search(neighbour,g+cost(node,neighbour),cutoff,route,depth+1);
					if ((t instanceof PathFinding.core.Node )){
						route[depth]=[node.x,node.y];
						return t;
					}
					if (_$this.trackRecursion && (--neighbour.retainCount)===0){
						neighbour.tested=false;
					}
					if (t < min){
						min=t;
					}
				}
				return min;
			}.bind(this);
			var start=grid.getNodeAt(startX,startY);
			var end=grid.getNodeAt(endX,endY);
			var cutOff=h(start,end);
			var j=0,route,t=0;
			for (j=0;true;++j){
				route=[];
				t=search(start,0,cutOff,route,0);
				if (t==Infinity){
					return [];
				}
				if ((t instanceof PathFinding.core.Node )){
					return route;
				}
				cutOff=t;
			}
		}

		return IDAStarFinder;
	})()


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.JumpPointFinderBase
	var JumpPointFinderBase=(function(){
		function JumpPointFinderBase(opt){
			this.grid=null;
			this.openList=null;
			this.startNode=null;
			this.endNode=null;
			this.heuristic=null;
			this.trackJumpRecursion=false;
			opt=opt || {};
			this.heuristic=opt.heuristic || Heuristic.manhattan;
			this.trackJumpRecursion=opt.trackJumpRecursion || false;
		}

		__class(JumpPointFinderBase,'PathFinding.finders.JumpPointFinderBase');
		var __proto=JumpPointFinderBase.prototype;
		/**
		*Find and return the path.
		*@return {Array<Array<number>>}The path,including both start and
		*end positions.
		*/
		__proto.findPath=function(startX,startY,endX,endY,grid){
			var openList=this.openList=new Heap(function(nodeA,nodeB){
				return nodeA.f-nodeB.f;
			}),startNode=this.startNode=grid.getNodeAt(startX,startY),endNode=this.endNode=grid.getNodeAt(endX,endY),node;
			this.grid=grid;
			startNode.g=0;
			startNode.f=0;
			openList.push(startNode);
			startNode.opened=true;
			while (!openList.empty()){
				node=openList.pop();
				node.closed=true;
				if (node==endNode){
					return Util.expandPath(Util.backtrace(endNode));
				}
				this._identifySuccessors(node);
			}
			return [];
		}

		/**
		*Identify successors for the given node. Runs a jump point search in the
		*direction of each available neighbor,adding any points found to the open
		*list.
		*@protected
		*/
		__proto._identifySuccessors=function(node){
			var grid=this.grid,heuristic=this.heuristic,openList=this.openList,endX=this.endNode.x,endY=this.endNode.y,neighbors,neighbor,jumpPoint,i=0,l=0,x=node.x,y=node.y,jx=0,jy=0,dx=0,dy=0,d=0,ng=0,jumpNode,abs=Math.abs,max=Math.max;
			neighbors=this._findNeighbors(node);
			for (i=0,l=neighbors.length;i < l;++i){
				neighbor=neighbors[i];
				jumpPoint=this._jump(neighbor[0],neighbor[1],x,y);
				if (jumpPoint){
					jx=jumpPoint[0];
					jy=jumpPoint[1];
					jumpNode=grid.getNodeAt(jx,jy);
					if (jumpNode.closed){
						continue ;
					}
					d=Heuristic.octile(abs(jx-x),abs(jy-y));
					ng=node.g+d;
					if (!jumpNode.opened || ng < jumpNode.g){
						jumpNode.g=ng;
						jumpNode.h=jumpNode.h || heuristic(abs(jx-endX),abs(jy-endY));
						jumpNode.f=jumpNode.g+jumpNode.h;
						jumpNode.parent=node;
						if (!jumpNode.opened){
							openList.push(jumpNode);
							jumpNode.opened=true;
						}
						else{
							openList.updateItem(jumpNode);
						}
					}
				}
			}
		}

		__proto._jump=function(x,y,px,py){}
		__proto._findNeighbors=function(node){}
		return JumpPointFinderBase;
	})()


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.JumpPointFinder
	var JumpPointFinder=(function(){
		/**
		*Path finder using the Jump Point Search algorithm
		*@param {Object}opt
		*@param {function}opt.heuristic Heuristic function to estimate the distance
		*(defaults to manhattan).
		*@param {DiagonalMovement}opt.diagonalMovement Condition under which diagonal
		*movement will be allowed.
		*/
		function JumpPointFinder(opt){
			opt=opt || {};
			if (opt.diagonalMovement===DiagonalMovement.Never){
				return new JPFNeverMoveDiagonally(opt);
			}
			else if (opt.diagonalMovement===DiagonalMovement.Always){
				return new JPFAlwaysMoveDiagonally(opt);
			}
			else if (opt.diagonalMovement===DiagonalMovement.OnlyWhenNoObstacles){
				return new JPFMoveDiagonallyIfNoObstacles(opt);
			}
			else{
				return new JPFMoveDiagonallyIfAtMostOneObstacle(opt);
			}
		}

		__class(JumpPointFinder,'PathFinding.finders.JumpPointFinder');
		return JumpPointFinder;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.finders.TraceFinder
	var TraceFinder=(function(){
		function TraceFinder(opt){
			this.allowDiagonal=false;
			this.dontCrossCorners=false;
			this.diagonalMovement=0;
			this.heuristic=null;
			opt=opt || {};
			this.allowDiagonal=opt.allowDiagonal;
			this.dontCrossCorners=opt.dontCrossCorners;
			this.heuristic=opt.heuristic || Heuristic.manhattan;
			this.diagonalMovement=opt.diagonalMovement;
			if (!this.diagonalMovement){
				if (!this.allowDiagonal){
					this.diagonalMovement=DiagonalMovement.Never;
				}
				else{
					if (this.dontCrossCorners){
						this.diagonalMovement=DiagonalMovement.OnlyWhenNoObstacles;
					}
					else{
						this.diagonalMovement=DiagonalMovement.IfAtMostOneObstacle;
					}
				}
			}
			if (this.diagonalMovement==DiagonalMovement.Never){
				this.heuristic=opt.heuristic || Heuristic.manhattan;
			}
			else{
				this.heuristic=opt.heuristic || Heuristic.octile;
			}
		}

		__class(TraceFinder,'PathFinding.finders.TraceFinder');
		var __proto=TraceFinder.prototype;
		__proto.findPath=function(startX,startY,endX,endY,grid){
			var openList=new Heap(function(nodeA,nodeB){
				return nodeA.f-nodeB.f;
			}),startNode=grid.getNodeAt(startX,startY),endNode=grid.getNodeAt(endX,endY),heuristic=this.heuristic,allowDiagonal=this.allowDiagonal,dontCrossCorners=this.dontCrossCorners,abs=Math.abs,SQRT2=Math.SQRT2,node,neighbors,neighbor,i=0,l=0,x=0,y=0,ng=0;
			startNode.g=0;
			startNode.f=0;
			openList.push(startNode);
			startNode.opened=true;
			while (!openList.empty()){
				node=openList.pop();
				node.closed=true;
				if (node===endNode){
					return Util.backtrace(endNode);
				}
				neighbors=grid.getNeighbors(node,this.diagonalMovement);
				for (i=0,l=neighbors.length;i < l;++i){
					neighbor=neighbors[i];
					if (neighbor.closed){
						continue ;
					}
					x=neighbor.x;
					y=neighbor.y;
					ng=node.g+((x-node.x===0 || y-node.y===0)? 1 :SQRT2);
					if (!neighbor.opened || ng < neighbor.g){
						neighbor.g=ng *l / 9;
						neighbor.h=neighbor.h || heuristic(abs(x-endX),abs(y-endY));
						neighbor.f=neighbor.g+neighbor.h;
						neighbor.parent=node;
						if (!neighbor.opened){
							openList.push(neighbor);
							neighbor.opened=true;
						}
						else{
							openList.updateItem(neighbor);
						}
					}
				}
			}
			return [];
		}

		return TraceFinder;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.libs.Heap
	var Heap=(function(){
		function Heap(cmp){
			this.cmp=null;
			this.nodes=null;
			this.heapFunction=new HeapFunction();
			this.cmp=cmp !=null ? cmp :this.heapFunction.defaultCmp;
			this.nodes=[];
		}

		__class(Heap,'PathFinding.libs.Heap');
		var __proto=Heap.prototype;
		__proto.push=function(x){
			return this.heapFunction.heappush(this.nodes,x,this.cmp);
		}

		__proto.pop=function(){
			return this.heapFunction.heappop(this.nodes,this.cmp);
		}

		__proto.peek=function(){
			return this.nodes[0];
		}

		__proto.contains=function(x){
			return this.nodes.indexOf(x)!==-1;
		}

		__proto.replace=function(x){
			return this.heapFunction.heapreplace(this.nodes,x,this.cmp);
		}

		__proto.pushpop=function(x){
			return this.heapFunction.heappushpop(this.nodes,x,this.cmp);
		}

		__proto.heapify=function(){
			return this.heapFunction.heapify(this.nodes,this.cmp);
		}

		__proto.updateItem=function(x){
			return this.heapFunction.updateItem(this.nodes,x,this.cmp);
		}

		__proto.clear=function(){
			return this.nodes=[];
		}

		__proto.empty=function(){
			return this.nodes.length===0;
		}

		__proto.size=function(){
			return this.nodes.length;
		}

		__proto.clone=function(){
			var heap=new Heap();
			heap.nodes=this.nodes.slice(0);
			return heap;
		}

		__proto.toArray=function(){
			return this.nodes.slice(0);
		}

		return Heap;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class PathFinding.libs.HeapFunction
	var HeapFunction=(function(){
		function HeapFunction(){
			this.defaultCmp=function(x,y){
				if (x < y){
					return-1;
				}
				if (x > y){
					return 1;
				}
				return 0;
			}
		}

		__class(HeapFunction,'PathFinding.libs.HeapFunction');
		var __proto=HeapFunction.prototype;
		//};
		__proto.insort=function(a,x,lo,hi,cmp){
			var mid=NaN;
			if (lo==null){
				lo=0;
			}
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			if (lo < 0){
				throw new Error('lo must be non-negative');
			}
			if (hi==null){
				hi=a.length;
			}
			while (lo < hi){
				mid=Math.floor((lo+hi)/ 2);
				if (cmp(x,a[mid])< 0){
					hi=mid;
				}
				else{
					lo=mid+1;
				}
			}
			return ([].splice.apply(a,[lo,lo-lo].concat(x)),x);
		}

		//};
		__proto.heappush=function(array,item,cmp){
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			array.push(item);
			return this._siftdown(array,0,array.length-1,cmp);
		}

		//};
		__proto.heappop=function(array,cmp){
			var lastelt,returnitem;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			lastelt=array.pop();
			if (array.length){
				returnitem=array[0];
				array[0]=lastelt;
				this._siftup(array,0,cmp);
			}
			else{
				returnitem=lastelt;
			}
			return returnitem;
		}

		//};
		__proto.heapreplace=function(array,item,cmp){
			var returnitem;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			returnitem=array[0];
			array[0]=item;
			this._siftup(array,0,cmp);
			return returnitem;
		}

		//};
		__proto.heappushpop=function(array,item,cmp){
			var _ref;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			if (array.length && cmp(array[0],item)< 0){
				_ref=[array[0],item],item=_ref[0],array[0]=_ref[1];
				this._siftup(array,0,cmp);
			}
			return item;
		}

		//};
		__proto.heapify=function(array,cmp){
			var i=0,_i=0,_j=0,_len=0,_ref,_ref1,_results,_results1;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			_ref1=(function(){
				_results1=[];
				for (_j=0,_ref=Math.floor(array.length / 2);0 <=_ref ? _j < _ref :_j > _ref;0 <=_ref ? _j++:_j--){
					_results1.push(_j);
				}
				return _results1;
			}).apply(this).reverse();
			_results=[];
			for (_i=0,_len=_ref1.length;_i < _len;_i++){
				i=_ref1[_i];
				_results.push(this._siftup(array,i,cmp));
			}
			return _results;
		}

		//};
		__proto.updateItem=function(array,item,cmp){
			var pos=0;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			pos=array.indexOf(item);
			if (pos===-1){
				return null;
			}
			this._siftdown(array,0,pos,cmp);
			return this._siftup(array,pos,cmp);
		}

		//};
		__proto.nlargest=function(array,n,cmp){
			var elem,result,_i=0,_len=0,_ref;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			result=array.slice(0,n);
			if (!result.length){
				return result;
			}
			this.heapify(result,cmp);
			_ref=array.slice(n);
			for (_i=0,_len=_ref.length;_i < _len;_i++){
				elem=_ref[_i];
				this.heappushpop(result,elem,cmp);
			}
			return result.sort(cmp).reverse();
		}

		//};
		__proto.nsmallest=function(array,n,cmp){
			var elem,i,los,result,_i=0,_j=0,_len,_ref,_ref1,_results;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			if (n *10 <=array.length){
				result=array.slice(0,n).sort(cmp);
				if (!result.length){
					return result;
				}
				los=result[result.length-1];
				_ref=array.slice(n);
				for (_i=0,_len=_ref.length;_i < _len;_i++){
					elem=_ref[_i];
					if (cmp(elem,los)< 0){
						this.insort(result,elem,0,null,cmp);
						result.pop();
						los=result[result.length-1];
					}
				}
				return result;
			}
			this.heapify(array,cmp);
			_results=[];
			for (i=_j=0,_ref1=Math.min(n,array.length);0 <=_ref1 ? _j < _ref1 :_j > _ref1;i=0 <=_ref1 ?++_j :--_j){
				_results.push(this.heappop(array,cmp));
			}
			return _results;
		}

		//};
		__proto._siftdown=function(array,startpos,pos,cmp){
			var newitem,parent,parentpos=0;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			newitem=array[pos];
			while (pos > startpos){
				parentpos=(pos-1)>> 1;
				parent=array[parentpos];
				if (cmp(newitem,parent)< 0){
					array[pos]=parent;
					pos=parentpos;
					continue ;
				}
				break ;
			}
			return array[pos]=newitem;
		}

		//};
		__proto._siftup=function(array,pos,cmp){
			var childpos=0,endpos=0,newitem,rightpos=0,startpos=0;
			if (cmp==null){
				cmp=this.defaultCmp;
			}
			endpos=array.length;
			startpos=pos;
			newitem=array[pos];
			childpos=2 *pos+1;
			while (childpos < endpos){
				rightpos=childpos+1;
				if (rightpos < endpos && !(cmp(array[childpos],array[rightpos])< 0)){
					childpos=rightpos;
				}
				array[pos]=array[childpos];
				pos=childpos;
				childpos=2 *pos+1;
			}
			array[pos]=newitem;
			return this._siftdown(array,startpos,pos,cmp);
		}

		return HeapFunction;
	})()


	/**
	*...
	*@author dongketao
	*/
	//class TestPathFinding
	var TestPathFinding=(function(){
		function TestPathFinding(){
			var opt={allowDiagonal:true,dontCrossCorners:false,heuristic:Heuristic["manhattan"],weight:1};
			var astart=new AStarFinder(opt);
			var grid=new Grid(64,36);
			var path=astart.findPath(23,16,33,16,grid);
			console.log(path.toString());
		}

		__class(TestPathFinding,'TestPathFinding');
		return TestPathFinding;
	})()


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.BestFirstFinder extends PathFinding.finders.AStarFinder
	var BestFirstFinder=(function(_super){
		function BestFirstFinder(opt){
			BestFirstFinder.__super.call(this,opt);
			var orig=this.heuristic;
			this.heuristic=function (dx,dy){
				return orig(dx,dy)*1000000;
			};
		}

		__class(BestFirstFinder,'PathFinding.finders.BestFirstFinder',_super);
		return BestFirstFinder;
	})(AStarFinder)


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.BiBestFirstFinder extends PathFinding.finders.BiAStarFinder
	var BiBestFirstFinder=(function(_super){
		function BiBestFirstFinder(opt){
			BiBestFirstFinder.__super.call(this,opt);
			var orig=this.heuristic;
			this.heuristic=function (dx,dy){
				return orig(dx,dy)*1000000;
			};
		}

		__class(BiBestFirstFinder,'PathFinding.finders.BiBestFirstFinder',_super);
		return BiBestFirstFinder;
	})(BiAStarFinder)


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.BiDijkstraFinder extends PathFinding.finders.BiAStarFinder
	var BiDijkstraFinder=(function(_super){
		function BiDijkstraFinder(opt){
			BiDijkstraFinder.__super.call(this,opt);
			this.heuristic=function (dx,dy){
				return 0;
			};
		}

		__class(BiDijkstraFinder,'PathFinding.finders.BiDijkstraFinder',_super);
		return BiDijkstraFinder;
	})(BiAStarFinder)


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.DijkstraFinder extends PathFinding.finders.AStarFinder
	var DijkstraFinder=(function(_super){
		function DijkstraFinder(opt){
			DijkstraFinder.__super.call(this,opt);
			this.heuristic=function (dx,dy){
				return 0;
			};
		}

		__class(DijkstraFinder,'PathFinding.finders.DijkstraFinder',_super);
		return DijkstraFinder;
	})(AStarFinder)


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.JPFAlwaysMoveDiagonally extends PathFinding.finders.JumpPointFinderBase
	var JPFAlwaysMoveDiagonally=(function(_super){
		function JPFAlwaysMoveDiagonally(opt){
			JPFAlwaysMoveDiagonally.__super.call(this,opt);
		}

		__class(JPFAlwaysMoveDiagonally,'PathFinding.finders.JPFAlwaysMoveDiagonally',_super);
		var __proto=JPFAlwaysMoveDiagonally.prototype;
		/**
		*Search recursively in the direction (parent-> child),stopping only when a
		*jump point is found.
		*@protected
		*@return {Array<Array<number>>}The x,y coordinate of the jump point
		*found,or null if not found
		*/
		__proto._jump=function(x,y,px,py){
			var grid=this.grid,dx=x-px,dy=y-py;
			if (!grid.isWalkableAt(x,y)){
				return null;
			}
			if (this.trackJumpRecursion==true){
				grid.getNodeAt(x,y).tested=true;
			}
			if (grid.getNodeAt(x,y)==this.endNode){
				return [x,y];
			}
			if (dx!==0 && dy!==0){
				if ((grid.isWalkableAt(x-dx,y+dy)&& !grid.isWalkableAt(x-dx,y))|| (grid.isWalkableAt(x+dx,y-dy)&& !grid.isWalkableAt(x,y-dy))){
					return [x,y];
				}
				if (this._jump(x+dx,y,x,y)|| this._jump(x,y+dy,x,y)){
					return [x,y];
				}
			}
			else{
				if (dx!==0){
					if ((grid.isWalkableAt(x+dx,y+1)&& !grid.isWalkableAt(x,y+1))|| (grid.isWalkableAt(x+dx,y-1)&& !grid.isWalkableAt(x,y-1))){
						return [x,y];
					}
				}
				else{
					if ((grid.isWalkableAt(x+1,y+dy)&& !grid.isWalkableAt(x+1,y))|| (grid.isWalkableAt(x-1,y+dy)&& !grid.isWalkableAt(x-1,y))){
						return [x,y];
					}
				}
			}
			return this._jump(x+dx,y+dy,x,y);
		}

		/**
		*Find the neighbors for the given node. If the node has a parent,
		*prune the neighbors based on the jump point search algorithm,otherwise
		*return all available neighbors.
		*@return {Array<Array<number>>}The neighbors found.
		*/
		__proto._findNeighbors=function(node){
			var parent=node.parent,x=node.x,y=node.y,grid=this.grid,px=0,py=0,nx=0,ny=0,dx=0,dy=0,neighbors=[],neighborNodes,neighborNode,i=0,l=0;
			if (parent){
				px=parent.x;
				py=parent.y;
				dx=(x-px)/ Math.max(Math.abs(x-px),1);
				dy=(y-py)/ Math.max(Math.abs(y-py),1);
				if (dx!==0 && dy!==0){
					if (grid.isWalkableAt(x,y+dy)){
						neighbors.push([x,y+dy]);
					}
					if (grid.isWalkableAt(x+dx,y)){
						neighbors.push([x+dx,y]);
					}
					if (grid.isWalkableAt(x+dx,y+dy)){
						neighbors.push([x+dx,y+dy]);
					}
					if (!grid.isWalkableAt(x-dx,y)){
						neighbors.push([x-dx,y+dy]);
					}
					if (!grid.isWalkableAt(x,y-dy)){
						neighbors.push([x+dx,y-dy]);
					}
				}
				else{
					if (dx===0){
						if (grid.isWalkableAt(x,y+dy)){
							neighbors.push([x,y+dy]);
						}
						if (!grid.isWalkableAt(x+1,y)){
							neighbors.push([x+1,y+dy]);
						}
						if (!grid.isWalkableAt(x-1,y)){
							neighbors.push([x-1,y+dy]);
						}
					}
					else{
						if (grid.isWalkableAt(x+dx,y)){
							neighbors.push([x+dx,y]);
						}
						if (!grid.isWalkableAt(x,y+1)){
							neighbors.push([x+dx,y+1]);
						}
						if (!grid.isWalkableAt(x,y-1)){
							neighbors.push([x+dx,y-1]);
						}
					}
				}
			}
			else{
				neighborNodes=grid.getNeighbors(node,DiagonalMovement.Always);
				for (i=0,l=neighborNodes.length;i < l;++i){
					neighborNode=neighborNodes[i];
					neighbors.push([neighborNode.x,neighborNode.y]);
				}
			}
			return neighbors;
		}

		return JPFAlwaysMoveDiagonally;
	})(JumpPointFinderBase)


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.JPFMoveDiagonallyIfAtMostOneObstacle extends PathFinding.finders.JumpPointFinderBase
	var JPFMoveDiagonallyIfAtMostOneObstacle=(function(_super){
		function JPFMoveDiagonallyIfAtMostOneObstacle(opt){
			JPFMoveDiagonallyIfAtMostOneObstacle.__super.call(this,opt);
		}

		__class(JPFMoveDiagonallyIfAtMostOneObstacle,'PathFinding.finders.JPFMoveDiagonallyIfAtMostOneObstacle',_super);
		var __proto=JPFMoveDiagonallyIfAtMostOneObstacle.prototype;
		/**
		*Search recursively in the direction (parent-> child),stopping only when a
		*jump point is found.
		*@protected
		*@return {Array<Array<number>>}The x,y coordinate of the jump point
		*found,or null if not found
		*/
		__proto._jump=function(x,y,px,py){
			var grid=this.grid,dx=x-px,dy=y-py;
			if (!grid.isWalkableAt(x,y)){
				return null;
			}
			if (this.trackJumpRecursion===true){
				grid.getNodeAt(x,y).tested=true;
			}
			if (grid.getNodeAt(x,y)==this.endNode){
				return [x,y];
			}
			if (dx!==0 && dy!==0){
				if ((grid.isWalkableAt(x-dx,y+dy)&& !grid.isWalkableAt(x-dx,y))|| (grid.isWalkableAt(x+dx,y-dy)&& !grid.isWalkableAt(x,y-dy))){
					return [x,y];
				}
				if (this._jump(x+dx,y,x,y)|| this._jump(x,y+dy,x,y)){
					return [x,y];
				}
			}
			else{
				if (dx!==0){
					if ((grid.isWalkableAt(x+dx,y+1)&& !grid.isWalkableAt(x,y+1))|| (grid.isWalkableAt(x+dx,y-1)&& !grid.isWalkableAt(x,y-1))){
						return [x,y];
					}
				}
				else{
					if ((grid.isWalkableAt(x+1,y+dy)&& !grid.isWalkableAt(x+1,y))|| (grid.isWalkableAt(x-1,y+dy)&& !grid.isWalkableAt(x-1,y))){
						return [x,y];
					}
				}
			}
			if (grid.isWalkableAt(x+dx,y)|| grid.isWalkableAt(x,y+dy)){
				return this._jump(x+dx,y+dy,x,y);
			}
			else{
				return null;
			}
		}

		/**
		*Find the neighbors for the given node. If the node has a parent,
		*prune the neighbors based on the jump point search algorithm,otherwise
		*return all available neighbors.
		*@return {Array<Array<number>>}The neighbors found.
		*/
		__proto._findNeighbors=function(node){
			var parent=node.parent,x=node.x,y=node.y,grid=this.grid,px=0,py=0,nx=0,ny=0,dx=0,dy=0,neighbors=[],neighborNodes,neighborNode,i=0,l=0;
			if (parent){
				px=parent.x;
				py=parent.y;
				dx=(x-px)/ Math.max(Math.abs(x-px),1);
				dy=(y-py)/ Math.max(Math.abs(y-py),1);
				if (dx!==0 && dy!==0){
					if (grid.isWalkableAt(x,y+dy)){
						neighbors.push([x,y+dy]);
					}
					if (grid.isWalkableAt(x+dx,y)){
						neighbors.push([x+dx,y]);
					}
					if (grid.isWalkableAt(x,y+dy)|| grid.isWalkableAt(x+dx,y)){
						neighbors.push([x+dx,y+dy]);
					}
					if (!grid.isWalkableAt(x-dx,y)&& grid.isWalkableAt(x,y+dy)){
						neighbors.push([x-dx,y+dy]);
					}
					if (!grid.isWalkableAt(x,y-dy)&& grid.isWalkableAt(x+dx,y)){
						neighbors.push([x+dx,y-dy]);
					}
				}
				else{
					if (dx===0){
						if (grid.isWalkableAt(x,y+dy)){
							neighbors.push([x,y+dy]);
							if (!grid.isWalkableAt(x+1,y)){
								neighbors.push([x+1,y+dy]);
							}
							if (!grid.isWalkableAt(x-1,y)){
								neighbors.push([x-1,y+dy]);
							}
						}
					}
					else{
						if (grid.isWalkableAt(x+dx,y)){
							neighbors.push([x+dx,y]);
							if (!grid.isWalkableAt(x,y+1)){
								neighbors.push([x+dx,y+1]);
							}
							if (!grid.isWalkableAt(x,y-1)){
								neighbors.push([x+dx,y-1]);
							}
						}
					}
				}
			}
			else{
				neighborNodes=grid.getNeighbors(node,DiagonalMovement.IfAtMostOneObstacle);
				for (i=0,l=neighborNodes.length;i < l;++i){
					neighborNode=neighborNodes[i];
					neighbors.push([neighborNode.x,neighborNode.y]);
				}
			}
			return neighbors;
		}

		return JPFMoveDiagonallyIfAtMostOneObstacle;
	})(JumpPointFinderBase)


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.JPFMoveDiagonallyIfNoObstacles extends PathFinding.finders.JumpPointFinderBase
	var JPFMoveDiagonallyIfNoObstacles=(function(_super){
		function JPFMoveDiagonallyIfNoObstacles(opt){
			JPFMoveDiagonallyIfNoObstacles.__super.call(this,opt);
		}

		__class(JPFMoveDiagonallyIfNoObstacles,'PathFinding.finders.JPFMoveDiagonallyIfNoObstacles',_super);
		var __proto=JPFMoveDiagonallyIfNoObstacles.prototype;
		/**
		*Search recursively in the direction (parent-> child),stopping only when a
		*jump point is found.
		*@protected
		*@return {Array<Array<number>>}The x,y coordinate of the jump point
		*found,or null if not found
		*/
		__proto._jump=function(x,y,px,py){
			var grid=this.grid,dx=x-px,dy=y-py;
			if (!grid.isWalkableAt(x,y)){
				return null;
			}
			if (this.trackJumpRecursion===true){
				grid.getNodeAt(x,y).tested=true;
			}
			if (grid.getNodeAt(x,y)===this.endNode){
				return [x,y];
			}
			if (dx!==0 && dy!==0){
				if (this._jump(x+dx,y,x,y)|| this._jump(x,y+dy,x,y)){
					return [x,y];
				}
			}
			else{
				if (dx!==0){
					if ((grid.isWalkableAt(x,y-1)&& !grid.isWalkableAt(x-dx,y-1))|| (grid.isWalkableAt(x,y+1)&& !grid.isWalkableAt(x-dx,y+1))){
						return [x,y];
					}
				}
				else if (dy!==0){
					if ((grid.isWalkableAt(x-1,y)&& !grid.isWalkableAt(x-1,y-dy))|| (grid.isWalkableAt(x+1,y)&& !grid.isWalkableAt(x+1,y-dy))){
						return [x,y];
					}
				}
			}
			if (grid.isWalkableAt(x+dx,y)&& grid.isWalkableAt(x,y+dy)){
				return this._jump(x+dx,y+dy,x,y);
			}
			else{
				return null;
			}
		}

		/**
		*Find the neighbors for the given node. If the node has a parent,
		*prune the neighbors based on the jump point search algorithm,otherwise
		*return all available neighbors.
		*@return {Array<Array<number>>}The neighbors found.
		*/
		__proto._findNeighbors=function(node){
			var parent=node.parent,x=node.x,y=node.y,grid=this.grid,px=0,py=0,nx=0,ny=0,dx=0,dy=0,neighbors=[],neighborNodes,neighborNode,i=0,l=0;
			if (parent){
				px=parent.x;
				py=parent.y;
				dx=(x-px)/ Math.max(Math.abs(x-px),1);
				dy=(y-py)/ Math.max(Math.abs(y-py),1);
				if (dx!==0 && dy!==0){
					if (grid.isWalkableAt(x,y+dy)){
						neighbors.push([x,y+dy]);
					}
					if (grid.isWalkableAt(x+dx,y)){
						neighbors.push([x+dx,y]);
					}
					if (grid.isWalkableAt(x,y+dy)&& grid.isWalkableAt(x+dx,y)){
						neighbors.push([x+dx,y+dy]);
					}
				}
				else{
					var isNextWalkable;
					if (dx!==0){
						isNextWalkable=grid.isWalkableAt(x+dx,y);
						var isTopWalkable=grid.isWalkableAt(x,y+1);
						var isBottomWalkable=grid.isWalkableAt(x,y-1);
						if (isNextWalkable){
							neighbors.push([x+dx,y]);
							if (isTopWalkable){
								neighbors.push([x+dx,y+1]);
							}
							if (isBottomWalkable){
								neighbors.push([x+dx,y-1]);
							}
						}
						if (isTopWalkable){
							neighbors.push([x,y+1]);
						}
						if (isBottomWalkable){
							neighbors.push([x,y-1]);
						}
					}
					else if (dy!==0){
						isNextWalkable=grid.isWalkableAt(x,y+dy);
						var isRightWalkable=grid.isWalkableAt(x+1,y);
						var isLeftWalkable=grid.isWalkableAt(x-1,y);
						if (isNextWalkable){
							neighbors.push([x,y+dy]);
							if (isRightWalkable){
								neighbors.push([x+1,y+dy]);
							}
							if (isLeftWalkable){
								neighbors.push([x-1,y+dy]);
							}
						}
						if (isRightWalkable){
							neighbors.push([x+1,y]);
						}
						if (isLeftWalkable){
							neighbors.push([x-1,y]);
						}
					}
				}
			}
			else{
				neighborNodes=grid.getNeighbors(node,DiagonalMovement.OnlyWhenNoObstacles);
				for (i=0,l=neighborNodes.length;i < l;++i){
					neighborNode=neighborNodes[i];
					neighbors.push([neighborNode.x,neighborNode.y]);
				}
			}
			return neighbors;
		}

		return JPFMoveDiagonallyIfNoObstacles;
	})(JumpPointFinderBase)


	/**
	*...
	*@author ...
	*/
	//class PathFinding.finders.JPFNeverMoveDiagonally extends PathFinding.finders.JumpPointFinderBase
	var JPFNeverMoveDiagonally=(function(_super){
		function JPFNeverMoveDiagonally(opt){
			JPFNeverMoveDiagonally.__super.call(this,opt);
		}

		__class(JPFNeverMoveDiagonally,'PathFinding.finders.JPFNeverMoveDiagonally',_super);
		var __proto=JPFNeverMoveDiagonally.prototype;
		/**
		*Search recursively in the direction (parent-> child),stopping only when a
		*jump point is found.
		*@protected
		*@return {Array<Array<number>>}The x,y coordinate of the jump point
		*found,or null if not found
		*/
		__proto._jump=function(x,y,px,py){
			var grid=this.grid,dx=x-px,dy=y-py;
			if (!grid.isWalkableAt(x,y)){
				return null;
			}
			if (this.trackJumpRecursion===true){
				grid.getNodeAt(x,y).tested=true;
			}
			if (grid.getNodeAt(x,y)==this.endNode){
				return [x,y];
			}
			if (dx!==0){
				if ((grid.isWalkableAt(x,y-1)&& !grid.isWalkableAt(x-dx,y-1))|| (grid.isWalkableAt(x,y+1)&& !grid.isWalkableAt(x-dx,y+1))){
					return [x,y];
				}
			}
			else if (dy!==0){
				if ((grid.isWalkableAt(x-1,y)&& !grid.isWalkableAt(x-1,y-dy))|| (grid.isWalkableAt(x+1,y)&& !grid.isWalkableAt(x+1,y-dy))){
					return [x,y];
				}
				if (this._jump(x+1,y,x,y)|| this._jump(x-1,y,x,y)){
					return [x,y];
				}
			}
			else{
				throw new Error("Only horizontal and vertical movements are allowed");
			}
			return this._jump(x+dx,y+dy,x,y);
		}

		/**
		*Find the neighbors for the given node. If the node has a parent,
		*prune the neighbors based on the jump point search algorithm,otherwise
		*return all available neighbors.
		*@return {Array<Array<number>>}The neighbors found.
		*/
		__proto._findNeighbors=function(node){
			var parent=node.parent,x=node.x,y=node.y,grid=this.grid,px=0,py=0,nx=0,ny=0,dx=0,dy=0,neighbors=[],neighborNodes,neighborNode,i=0,l=0;
			if (parent){
				px=parent.x;
				py=parent.y;
				dx=(x-px)/ Math.max(Math.abs(x-px),1);
				dy=(y-py)/ Math.max(Math.abs(y-py),1);
				if (dx!==0){
					if (grid.isWalkableAt(x,y-1)){
						neighbors.push([x,y-1]);
					}
					if (grid.isWalkableAt(x,y+1)){
						neighbors.push([x,y+1]);
					}
					if (grid.isWalkableAt(x+dx,y)){
						neighbors.push([x+dx,y]);
					}
				}
				else if (dy!==0){
					if (grid.isWalkableAt(x-1,y)){
						neighbors.push([x-1,y]);
					}
					if (grid.isWalkableAt(x+1,y)){
						neighbors.push([x+1,y]);
					}
					if (grid.isWalkableAt(x,y+dy)){
						neighbors.push([x,y+dy]);
					}
				}
			}
			else{
				neighborNodes=grid.getNeighbors(node,DiagonalMovement.Never);
				for (i=0,l=neighborNodes.length;i < l;++i){
					neighborNode=neighborNodes[i];
					neighbors.push([neighborNode.x,neighborNode.y]);
				}
			}
			return neighbors;
		}

		return JPFNeverMoveDiagonally;
	})(JumpPointFinderBase)



})(window,document,Laya);
